Virtual Talk with Gaurav Rattan
Abstract
Graphs and networks form a fundamental data modality of our times, taking their rightful place among more primitive data types such as vectors, text and images. The early advances in Graph ML mainly focused on extracting such primitive data from graphs, in order to reuse existing ML models for such data. The recent success of Graph Neural Networks (GNNs) has sparked a huge interest in designing novel graph learning methods based on graph-centric principles, as opposed to the earlier approach. The key questions in this context are: What kind of structural information does a GNN extract from a graph? Perhaps, more importantly, what kind of information should a graph learning model extract from a graph?
In this talk, we answer these questions using classical tools from graph theory and discrete algorithms. Based on our results, we develop a surprising three-fold correspondence between: (1) counting motifs in networks, (2) graph isomorphism testing, and (3) the expressive power of GNNs. These results provide a strong characterization of the structural information captured by GNNs. We then show how these results allow us to derive novel GNNs with provably higher expressive and predictive power. Finally, we discuss concrete applications of our results, ranging from molecular networks in chemistry to data-driven optimization for SAT/CSP.
Bio
Gaurav Rattan is a post-doctoral researcher in the Department of Mathematics at Technische Universität Darmstadt since April 2023. His main research interests lie in developing machine learning algorithms for graphs and networks, in particular, graph neural networks. His research focuses on combining techniques from classical graph theory and discrete algorithms towards the design and analysis of graph neural networks.
Previously, he worked as a DFG Eigene Stelle researcher since April 2019 in the Department of Computer Science at RWTH Aachen University. Earlier, he obtained a Ph.D. in Theoretical Computer Science at IMSc Chennai (India), following his undergraduate studies at IIT Bombay, Mumbai (India).
Zoom Registration
Please register with office@c3s.uni-frankfurt.de to receive the Zoom login.